﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0171_Multiply : IAlgorithm
    {
        // 43. 字符串相乘

        // 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
        // 注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。


        public void Test()
        {
            // 算法参数定义
            string num1 = "321", num2 = "21";
            // 算法执行与打印
            Console.WriteLine(Multiply(num1, num2));
            //var res = Algorithm(param);
            //foreach (var item in res)
            //{
            //    foreach (var iitem in item)
            //    {
            //        Console.Write(iitem + " ");
            //    }
            //    Console.WriteLine();
            //}
        }

        // 算法
        public string Multiply(string num1, string num2)
        {
            if (num1.Equals("0") || num2.Equals("0"))
                return "0";
            int m = num1.Length, n = num2.Length;
            int[] ansArr = new int[m + n];
            for (int i = m - 1; i >= 0; i--)
            {
                int x = num1[i] - '0';
                for (int j = n - 1; j >= 0; j--)
                {
                    int y = num2[j] - '0';
                    ansArr[i + j + 1] += x * y;
                }
            }
            for (int i = m + n - 1; i > 0; i--)
            {
                ansArr[i - 1] += ansArr[i] / 10;
                ansArr[i] %= 10;
            }
            int index = ansArr[0] == 0 ? 1 : 0;
            StringBuilder ans = new StringBuilder();
            while (index < m + n)
            {
                ans.Append(ansArr[index]);
                index++;
            }
            return ans.ToString();

        }
    }
}
